public class MyHashBucket {

    static class Node {
        int key;
        Node next;

        public Node(int key) {
            this.key = key;
        }
    }

    //初始容量默认为10
    private Node[] arr = new Node[10];
    private int size; //当前插入的元素个数
    private static final double DEFAULT_LOAD_FACTOR = 0.75;  //默认的负载因子

    public void insert(int key) {
        //计算哈希地址,使用Math,abs()方法是为了防止插入值是负数的情况！
        int index = Math.abs(key) % arr.length;
        Node cur = arr[index];

        //开始遍历，查看哈希表是否有重复
        while (cur != null) {
            if (cur.key == key) {
                return;
            }
            cur = cur.next;
        }

        //哈希表没有重复
        //进行头插，即使一开始为空链表也可以
        Node node = new Node(key);
        node.next = arr[index];
        arr[index] = node;
        size++;

        //判断是否需要扩容
        if (doLoadFactor() >= DEFAULT_LOAD_FACTOR) {
            resize();
        }
    }

    //求当前哈希表负载因子
    private double doLoadFactor() {
        return size*1.0/arr.length;
    }

    //扩容操作
    private void resize() {
        Node[] newArr = new Node[2*arr.length];
        //遍历原哈希表的每一个元素，并放入新的哈希表中
        for (int i = 0; i < arr.length; i++) {
            Node cur = arr[i];
            while (cur != null) {
                //计算新的哈希地址
                int newIndex = Math.abs(cur.key) % newArr.length;

                //保存cur的下一个位置
                Node curN = cur.next;

                //将cur放入新的哈希表中的桶
                cur.next = newArr[newIndex];
                newArr[newIndex] = cur;

                cur = curN;
            }
        }

        //更新哈希表
        arr = newArr;
    }

    public boolean find(int key) {
        int index = Math.abs(key) % arr.length;
        Node cur = arr[index];
        while (cur != null) {
            if (cur.key == key) {
                return true;
            }
            cur = cur.next;
        }

        return false;
    }

    public boolean remove(int key) {
        int index = Math.abs(key) % arr.length;
        Node cur = arr[index];
        Node prev = null;  //记录cur的前一个节点
        while (cur != null) {
            if (cur.key == key) {
                break;
            }
            prev = cur;
            cur = cur.next;
        }

        //cur == null说明哈希表没有这个元素
        if (cur == null) {
            return false;
        }

        //如果要删除的值位于头节点
        if (cur == arr[index]) {
            arr[index] = cur.next;
            size--;
            return true;
        }

        //位于尾节点和中间节点的情况：
        prev.next = cur.next;
        size--;
        return true;
    }
}
